class HashTable<T = any> {
    // 创建一个数组，用来存放链表地址中的链(数组),这里string是键的类型，T是value的类型，其是一个元组类型，然后其放在一个数组里面，再放入另一个数组里面
    // 数组里面放数组，然后数组里面的每一项都是元组
    storage: [string,T][][] = [];
    // 定义数组的长度，count/length 为哪个什么因子，大于0.75提醒扩容(增加数组长度)
    private length: number = 7;
    // 记录已经存在的元素的个数
    private count: number = 0;

    private hashFunc(key: string, max:number):number{ 
        let hashCode = 0;
        const length = key.length;
        for (let i = 0; i < length; i++) {
            // 公式
            hashCode = 31 * hashCode + key.charCodeAt(i);
        }
        // 计算出索引值
        const index = hashCode % max;
    
        return index
    }


     isPrime(num:number):boolean {
        // 质数的特点, 只能被1和自身整除
        // 这里比如传递进来的是8
        // 下面就是判断其是否能被2到其之间的数整除2 -7
        // 只需要判断数字对应的平方根之前的数字是否能被整除即可，因为要想乘以其他数据得到结果，就必须要有一个数字是在其平方根之下的
    
        const sqrt = Math.sqrt(num)
    
        for( let i = 2; i <= sqrt; i++ ) {
            if(num % i == 0 ) return false
        }
    
        return true
    }

    private getNextPrime(num: number) {
        // 确定newLength是一个质数，质数会让桶里面的数据平均分配
        let newLength = num;
        while(!this.isPrime(newLength) ){
            newLength ++;
        }
        return newLength;
    }
    // 扩容缩容
    private resize(newLength:number){

        let newPrime = this.getNextPrime(newLength)

        if(newPrime < 7 ) {
            console.log('oooo')
            newPrime = 7
        };
        console.log('newPrime',newPrime)


        //设置新的长度
        this.length = newPrime;
        //获取原来的数据，并将数据重新放在新的容量的数组里面
        // 1、对数据进行初始化
        const oldStorage = this.storage;
        this.storage = [];
        this.count = 0;
        
        //2、获取原来数据
        oldStorage.forEach(bucket => {
            if(!bucket) return;
            for(let i = 0; i < bucket.length; i++){
                const tuple = bucket[i];
                this.put(tuple[0],tuple[1])
            }

        })

    }
    //插入-修改
    put(key:string,value:T){
        // 1.根据key获取数组的索引值
        const index = this.hashFunc(key,this.length);

        // 2.根据索引取出对应的数组
        let bucket = this.storage[index];

        // 3.判断bucket是否有值
        if(!bucket){
            bucket = [];
            this.storage[index] = bucket;
        }
        // 记录是否发生覆盖
        let isUpdate = false;
        // 4.确定已经有一个数组，但是数组里面是否已存在key是不确定的
        for(let i = 0; i < bucket.length; i++){
            const tuple = bucket[i]
            const tupleKey = tuple[0];//key
            //tuple[1]是value
            if(tupleKey === key){
                //修改操作
                tuple[1]= value;
                isUpdate = true
            }
        }
        // 表示没有发生过覆盖
        if(!isUpdate){
            bucket.push([key,value]);

            this.count++;
             // 如果loadFactor 大于0.75 ,扩容操作
            const loadFactor = this.count / this.length;
            if(loadFactor > 0.75){
                this.resize(this.length * 2)
            }
        }
    }
    
    // 获取值
    get(key: string) : T | undefined {
        // 1、根据key 获取索引值index
        const index = this.hashFunc(key,this.length)

        // 2、获取bucket(桶)
        const bucket = this.storage[index]
        // 如果桶不存在，直接返回undefined
        if(!bucket) return undefined;

        //3、对桶进行遍历
        for (let i = 0; i < bucket.length; i++){
            const tuple = bucket[i];
            let tupleKey = tuple[0];
            let tupleValue = tuple[1];
            if(tupleKey === key){
                return tupleValue
            }
            return undefined
        }
    }

    // 删除操作
    delete(key: string): T | undefined {
        // 1、获取索引值位置
        const index = this.hashFunc(key,this.length);

        // 2、获取 bucket(桶)
        const bucket = this.storage[index];
        if(!bucket) return undefined;

        // 3、遍历桶数组
        for(let i = 0 ; i < bucket.length; i++){
            const tuple = bucket[i];
            const tupleKey = tuple[0];
            const tupleValue = tuple[1];
            if(tupleKey === key){
                //删除当前项
                bucket.splice(i, 1);
                this.count--;
                // 如果loadFactor 小于0.25 ,缩容操作
                const loadFactor = this.count / this.length;
                if(loadFactor < 0.25 && this.length > 7){
                    this.resize(Math.floor(this.length / 2))
                }
                return tupleValue
            }
        }
        return undefined
    }
}

const hashTable = new HashTable();

hashTable.put('aaa',100);
hashTable.put('aaa',200);
hashTable.put('bbb',300);
hashTable.put('ccc',400);
hashTable.put('ddd',500);
hashTable.put('eee',600);
hashTable.put('fff',700);
hashTable.put('ggg',800);

console.log(hashTable.storage)

// console.log(hashTable.get('aaa'));

// console.log(hashTable.get('bbb'));

// console.log(hashTable.get('abc'));

// console.log(hashTable.get('ddd'));

console.log('dddd',hashTable.delete('aaa'))
console.log('dddd',hashTable.delete('bbb'))
console.log('dddd',hashTable.delete('ccc'))
console.log('dddd',hashTable.delete('ddd'))
console.log('dddd',hashTable.delete('fff'))
console.log('dddd',hashTable.delete('eee'))
console.log(hashTable.storage)


// console.log('rrrr',hashTable.get('aaa'));


export default {}


// 原组类型放在数组里面再放入数组里面
// let tuple:[number,number][][] = [[[111,2222]]]